import java.util.*;

class ListNode {
     int val;
     ListNode next;
     ListNode(int x) {
         val = x;
         next = null;
     }
}

public class RemoveDuplicatesFromSortedList {
    
    public static ListNode deleteDuplicates(ListNode head) {
        if(head == null) return null;
        if(head.next == null) return head;
        
        HashSet<Integer> set = new HashSet<Integer>();
        
        ListNode p1 = head;
        ListNode p = head.next;
        ListNode p2 = null;

        set.add(p1.val);

        while(p!=null){

            if(set.contains(p.val)) {
                p1.next = p.next;
                p2 = p;
            }
            else{
                set.add(p.val);
                p1=p;
                p2 = null;
            }
                
            p=p.next;
            
            if(p2!=null) p2.next = null;
        }

        return head;
    }
    
    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(1);
        ListNode n3 = new ListNode(2);
        ListNode n4 = new ListNode(2);

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;

        ListNode head = deleteDuplicates(n1);

        while(head != null){
            System.out.println(head.val);
            head=head.next;
        }

        
    }
}
